﻿#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<unordered_map>
#include<unordered_set>

using namespace std;

class Solution {
public:

    unordered_map<char, unordered_set<char>>hash;//用来存字符先后关系
    unordered_map<char, int>in;//用来存入度
    bool cheak = false;

    void add(string front, string back)
    {
        int j = 0;
        while (j < front.size() && j < back.size())
        {
            int a = front[j]; int b = back[j];
            if (a == b)j++;
            else
            {
                if (!hash.count(a) || !hash[a].count(b))
                {
                    hash[a].insert(b);
                    in[b]++;
                }
                cheak = false;
                break;
            }
            if (j == back.size() && j < front.size())cheak = true;//前一个单词比后一个长，后一个是前一个的前缀，不合法
        }
    }

    string alienOrder(vector<string>& words) {
        if (words.size() == 1)return words[0];
        for (auto str : words)
        {
            for (auto ch : str)
            {
                in[ch] = 0;//初始化入度表，把出现的字符都插入表中并且把入度值初始化为0
            }
        }

        for (int i = 0; i < words.size(); i++)//更新连接关系与入度
        {
            for (int j = i + 1; j < words.size(); j++)
            {
                string frontwords = words[i];
                string backwords = words[j];
                add(frontwords, backwords);
                if (cheak)return "";
            }
        }

        //拓扑排序过程
        string ret;
        queue<char>q;
        for (auto& e : in)//把入度为零的点先插入
        {
            if (e.second == 0)
            {
                q.push(e.first);
            }
        }
        while (!q.empty())
        {
            char top = q.front(); q.pop();
            ret += top;
            for (auto& e : hash[top])
            {
                in[e]--;
                if (in[e] == 0)q.push(e);
            }
        }

        for (auto& e : in)
        {
            if (e.second != 0)return "";
        }

        return ret;
    }
};


//class Solution {
//    unordered_map<char, unordered_set<char>> edges; // 邻接表来存储图
//    unordered_map<char, int> in;                    // 统计⼊度
//    bool cheak;                                     // 处理边界情况
//public:
//    string alienOrder(vector<string>& words) {
//        // 1. 建图 + 初始化⼊度哈希表
//        for (auto& s : words) {
//            for (auto ch : s) {
//                in[ch] = 0;
//            }
//        }
//        int n = words.size();
//        for (int i = 0; i < n; i++) {
//            for (int j = i + 1; j < n; j++) {
//                add(words[i], words[j]);
//                if (cheak)
//                    return "";
//            }
//        }
//
//        // 2. 拓扑排序
//        queue<char> q;
//        for (auto& [a, b] : in) {
//            if (b == 0)
//                q.push(a);
//        }
//        string ret;
//        while (q.size()) {
//            char t = q.front();
//            q.pop();
//            ret += t;
//            for (char ch : edges[t]) {
//                if (--in[ch] == 0)
//                    q.push(ch);
//            }
//        }
//        // 3. 判断
//        for (auto& [a, b] : in)
//            if (b != 0)
//                return "";
//
//        return ret;
//    }
//    void add(string& s1, string& s2) {
//        int n = min(s1.size(), s2.size());
//        int i = 0;
//        for (; i < n; i++) {
//            if (s1[i] != s2[i]) {
//                char a = s1[i], b = s2[i]; // a -> b
//                if (!edges.count(a) || !edges[a].count(b)) {
//                    edges[a].insert(b);
//                    in[b]++;
//                }
//                break;
//            }
//        }
//        if (i == s2.size() && i < s1.size())
//            cheak = true;
//    }
//};
